package Midium;

//33.搜索旋转排序数组
public class Solution33 {
    public int search(int[] nums, int target) {
        if (nums.length == 1) {
            if (nums[0] == target)
                return 0;
            else
                return -1;
        }
        if (nums[0] < nums[nums.length - 1]) {
            //说明旋转点在起始位置，直接二分法查找
            return find(nums,0,nums.length-1,target);
        } else {
            //寻找旋转点的位置
            int point = -1;
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] > nums[i + 1]) {
                    if(nums[i]==target)
                        return i;
                    point = i + 1;
                    break;
                }
            }
            if (target == nums[point])
                return point;
            else if (target < nums[point])
                return -1;
            else {
                //target>nums[point]
                if (target > nums[nums.length - 1]) {
                    //在[0,point)里找
                    return find(nums,0,point-1,target);
                } else {
                    //在(point,nums.length-1]里找
                    return find(nums,point+1,nums.length-1,target);
                }
            }
        }
    }

    //二分法查找元素
    public static int find(int[] nums, int l, int r, int target) {
        if(l>r)
            return -1;
        int mid = (l+r)/2;
        if(nums[mid]==target)
            return mid;
        if(target>nums[mid]){
            return find(nums,mid+1,r,target);
        }else {
            return find(nums,l,mid-1,target);
        }
    }
}
